수학 수식 테스트

graph TD A[Start] --> B{Is it working?} B -- Yes --> C[Great!] B -- No --> D[Fix it] D --> B \[f_{w,b}(X) = w \cdot X + b\]

알고리즘 · 2025-04-30

다익스트라 알고리즘

다익스트라 알고리즘 다익스트라 알고리즘이란, 가중치가 음수가 아닌 그래프에서 임의의 한 노드로부터 다른 모든 노드들로의 최소 거리를 구하는 알고리즘입니다. 알고리즘의 각 단계는 다음과 같습니다. 출발 노드 : K, 노드 a 에서 노드 b 까지 거리 : distance[a][b] 1. 각 노드로의 최소 거리를 저장할 배열 dist를 만들고, 값을 INF로 초기화 시킵니다. dist[K]의 경우 0을 저장합니다. (INF란 해당 타입이 지원하는 가장 큰 값, 또는 단순히 매우 큰 값입니다.) 2. 현재 노드 K와 연결된 다른 임의의 노드 N이 있을 경우, dist[N]의 값과 dist[K] + distance[K][N]의 값을 비교하여, 후자의 값이 더 작을 경우, dist[K]의 값을 dist[K] + distance[K][N]로 업데이트 합니다. 3. 현재 노드 K와 연결된 모든 노드들에 대하여 단계 2를 수행합니다. 4. 현재 노드 K와 연결된 노드들 중 거리가 가장 짧은 노드로 이동하여 단계 2 ~ 3을 진행합니다. 5. 모든 노드를 방문할 때까지 이를 진행합니다. 예시 다음과 같은 임의의 방향 그래프가 있습니다. 노드 1로부터 다른 노드들로의 최소 거리를 구해보도록 하곘습니다. i dist$[i]$ 1 0 2 INF 3 INF 4 INF 현재 노드 1과 연결된 노드가 2와 3이 있습니다. 여기서 이 두 노드로의 최소 거리를 구해보도록 하겠습니다. 먼저 현재 노드 1에 대하여 연결된 각 노드에 대해 다음의 비교를 진행해 줍니다. 예를 들어 노드 2의 경우, dist$[2]$(현재 저장된 노드 2로의 최소거리) 와, 노드 1까지의 최소거리와 노드 1부터 노드 2까지의 거리의 합 ( dist$[1]$ + distance$[1][2]$ ) 을 비교합니다. 지금의 경우, dist$[2]$ 는 INF 의 값을 가지고 있기 때문에, dist$[1]$ + distance$[1][2]$ ( 0 + 2 = 2 ) 의 값으로 업데이트 됩니다. 노드 3도 마찬가지로 dist$[3]$ (INF) > dist$[1]$ (0) + distance$[1][3]$ ( 3 ) 이므로 dist$[3]$의 값도 3으로 업데이트 됩니다. i dist$[i]$ 1 0 2 2 3 3 4 INF 이제 노드 1과 연결된 노드 2로 이동하여 같은 단계를 반복합니다. 노드 2와 연결된 노드 3에 대하여, 노드 1에서 노드 3으로 가는 거리가 더 짧은지, 아니면 노드 1에서 노드 2를 거쳐 노드 3으로 가는 거리 더 짧은지 확인합니다. dist$[3]$ (3) 의 값과 dist$[2]$ (2) + distance$[2][3]$ (4) 를 비교했을 때, 전자의 값이 더 작으므로, dist$[3]$의 값은 그대로 유지됩니다. 노드 2와 연결된 노드 4의 경우, dist$[4]$의 값은 INF로 저장되어 있어, dist$[2]$ (2) + distance$[2][4]$ (5) 의 값이 저장됩니다. i dist$[i]$ 1 0 2 2 3 3 4 7 노드 3으로 이동하여 똑같이 수행합니다. 기존에 저장된 dist$[2]$의 값과 현재 노드 3을 거쳐 노드 2로 가는 것 중 어느 것으 더 짧은지 비교합니다. dist$[2]$ (2) < dist$[3]$ (3) + distance$[3][2]$ (4)의 값을 비교하였을 때, 전자의 값이 더 작으므로, dist$[2]$의 값은 유지됩니다. 다음으로 연결된 노드 4와도 비교하는데, dist$[4]$ (7) 의 값과 dist$[3]$ (3) + distance$[3][4]$ (6) 의 값 중 전자의 값이 더 작으므로, dist$[4]$의 값은 그대로 유지됩니다. 최종적으로 각 노드로의 최소 거리는 다음과 같습니다. i dist$[i$ 1 0 2 2 3 3 4 7 p. 1753 최단경로 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 출력 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다. 제가 다익스트라 알고리즘을 알게 해준 아주 고마운 문제입니다…. 보통 다익스트라 알고리즘을 구현할 때 자주 사용되는 것이 우선순위 큐 입니다. 기존의 그래프 탐색 방법인 bfs와 비슷하게, 방문한 노드를 큐에 저장하여 탐색을 진행합니다. 그러나 조금 다른 점은 우선순위 큐에 각 노드와의 거리를 -기호를 붙여 음수의 형태로 저장합니다. 그렇게 될 경우, 절댓값이 가장 작은 값, 즉 가장 거리가 짧은 노드가 우선순위 큐의 top에 위치하게 되어, 그래프 탐색을 진행합니다. 코드는 다음과 같습니다. Code #include<iostream> #include<vector> #include<queue> using namespace std; #define MAX 20001 #define INF 210000000 int V,E,K; vector<pair<int,int>> graph[MAX]; priority_queue<pair<int, int>> pq; int _min[MAX]; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> V >> E >> K; while(E--){ int u, v, w; cin >> u >> v >> w; graph[u].push_back({v,w}); } for(int i = 1; i <= V; i++) _min[i] = INF; pq.push({0, K}), _min[K] = 0; while(!pq.empty()){ int cur = pq.top().second; int distance = -pq.top().first; pq.pop(); for(int i = 0; i < graph[cur].size(); i++){ int next = graph[cur][i].first; int nextDistance = graph[cur][i].second; if(_min[next] > distance + nextDistance) _min[next] = distance + nextDistance, pq.push({-_min[next], next}); } } for(int i = 1; i <= V; i++){ if(_min[i] == INF) cout << "INF" << '\n'; else cout << _min[i] << '\n'; } } 메모리 시간 9184 KB 88 ms 사실 이 문제는 제가 굉장히 애를 썼던 문제였습니다. 처음 봤을 때는 쉬운 문제겠구나 싶었는데, 생각보다 어떻게 해야할 지 애를 먹었습니다… 그러던 중 다익스트라 알고리즘을 알게 되었고, 간단히 풀 수 있었습니다… p. 1916 최소비용 구하기 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다. 출력 첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다. 위의 p. 1753 최단경로 문제와 같은 문제입니다. 여기서 다른 점은 위의 문제는 모든 노드로의 최소 경로를 구했다면, 이 문제는 특정 노드로의 최소 경로를 구하면 되는 문제입니다. 코드는 다음과 같습니다. Code #include<iostream> #include<vector> #include<queue> #define MAX 1001 #define INF 210000000 using namespace std; int N, M, start, _end; vector<pair<int, int>> buses[MAX]; priority_queue<pair<int, int>> pq; int smallest[MAX]; int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> N >> M; while(M--){ int cost; cin >> start >> _end >> cost; buses[start].push_back({_end, cost}); } for(int i = 1; i <= N; i++) smallest[i] = INF; cin >> start >> _end; pq.push({0, start}), smallest[start] = 0; while(!pq.empty()){ int cur = pq.top().second; int cost = -pq.top().first; pq.pop(); if(cost > smallest[cur]) continue; for(int i = 0; i < buses[cur].size(); i++){ int next = buses[cur][i].first; int nextCost = buses[cur][i].second; if(smallest[next] > nextCost + cost) smallest[next] = nextCost + cost, pq.push({-smallest[next], next}); } } cout << smallest[_end]; return 0; } 메모리 시간 4744 KB 28 ms

알고리즘 · 2024-09-04

AVL 트리

Data Structure · 2024-07-07

이진 트리

Binary Tree Tree란 노드의 집합에 의한 계층적 자료구조입니다. 각 노드들은 데이터 값과 자식 노드라고 칭하는 노드들의 포인터 값을 가집니다. 그리고 자신의 포인터 값을 가지고 있는 노드를 부모노드라고 합니다. 트리의 각 노드는 세 가지로 분류될 수 있습니다. 루트 노드 ( Root Node ) : 부모노드를 갖지 않는 경우 말단 노드 ( Leaf Node ) : 자녀노드를 갖지 않는 경우 내부 노드 ( Internal Node ) : 위의 두 경우를 제외한 경우 그리고 자신과 같은 부모 노드를 가지고 있는 노드들을 형제 ( Sibling ) 노드 라고 합니다. 차수 ( Degree, = d ) : 자식 노드의 개수 Level ( = Height ) : 루트 노드는 0 또는 1부터 시작하여, 자식노드는 부모노드보다 1을 더한 값을 얻는다. 이진 트리 ( Binary Tree ) 이진 트리 ( Binary Tree )는 차수가 2 이하인 트리를 말합니다. 그 안에도 여러 종류가 있습니다. 편향 이진 트리 ( Skewed Binary Tree ) 말단 노드를 제외한 모든 노드가 오직 한개의 자식 노드를 갖는 트리를 말합니다. Degenerate Tree 라고도 합니다. 이 경우엔 연결리스트와 같은 기능을 가집니다. 정 이진 트리 ( Full Binary Tree ) 말단 노드를 제외한 모든 노드의 차수가 0 또는 2인 트리를 말합니다. 완전 이진 트리 ( Complete Binary Tree ) 말단 노드를 제외한 모든 노드의 차수가 2인 트리를 말합니다. 또한 마지막 레벨을 제외한 모든 레벨이 채워져 있어야 합니다. 즉, 말단 노드들의 레벨 차이는 최대 1 입니다. 말단 노드들은 트리에 채워질 때, 왼쪽부터 채워집니다. 포화 이진 트리 ( Perfect Binary Tree ) 완전 이진 트리에서 마지막 레벨이 모두 채워진 경우를 포화 이진 트리라고 합니다. 즉, 모든 말단 노드의 레벨이 같습니다. 이진 탐색 트리 (Binary Search Tree, BST) 이진 탐색 트리는 이진 탐색 알고리즘을 트리에 접목시킨 것입니다. 각 노드의 데이터보다 작은 값은 왼쪽 부분 트리로, 큰 값은 오른쪽 부분 트리로 저장됩니다. 특정 값 n을 찾을 때, 현재 노드의 데이터보다 작다면 왼쪽 자식 노드, 크다면 오른쪽 자식 노드로 이동해서 재귀적으로 진행되기 때문에, 이진 탐색과 같이 삽입, 삭제, 탐색 연산이 모두 $O(log_2N)$이 됩니다. 탐색 연산 find “key” 루트 노드부터 탐색을 시작합니다. 노드의 값 == key 이면, 탐색 성공, 종료 노드의 값 < key 이면, 왼쪽 자식 노드로 이동 노드의 값 > key 이면, 오른쪽 자식 노드로 이동 이 과정을 반복하였을 때, 마지막에 key 값과 같은 값을 가진 노드가 존재하지 않다면 탐색 실패로 종료됩니다. 삽입 연산 insert “key” 삽입 연산이 이루어지기 위해서 탐색 연산을 시작합니다. 탐색이 종료되는 경우, 탐색이 종료된 위치에 키 값을 삽입합니다. 삭제 연산 delete “key” 탐색 연산을 시작합니다. 탐색이 실패하면 어떠한 행동도 취하지 않습니다. 탐색이 성공하면 해당 노드를 삭제합니다. 해당 노드가 말단 노드인 경우 : 해당 노드를 삭제합니다. 해당 노드가 하나의 자식 노드를 가지는 경우 : 해당 노드를 삭제하고, 자식 노드로 이를 대체합니다. 해당 노드가 두개의 자식 노드를 가지는 경우 : 해당 노드를 삭제하고, 다음 중 하나의 노드를 골라 이를 대체합니다. 왼쪽 부분 트리에서 가장 큰 값을 가지는 노드 오른쪽 부분 트리에서 가장 작은 값을 가지는 노드 이제 BST를 구현해보도록 하겠습니다. code #include<iostream> #include<ostream> #define inorder 0 #define preorder 1 #define postorder 2 using namespace std; class Underflow {}; template <typename T> class Node { public: T data; Node<T> *left, *right; Node<T>() : left(nullptr), right(nullptr) {} Node<T>(T value) : data(value), left(nullptr), right(nullptr) {} }; template <typename T> class BinaryTree { public: int size; Node<T> *root; BinaryTree<T>() : size(0) , root(nullptr) {} void insert(T value){ insertNode(value, root); size++; } bool search(T value){ return searchNode(value, root); } void remove(T value){ try{ if(size <= 0) throw Underflow(); removeNode(value, root); size--; cout << "\nremoved " << value << '\n'; } catch(Underflow e){ cout << "underflow occurs" << '\n'; exit(0); } } void print(int N){ if(N == inorder){ cout << "inorder : "; inOrder(root); } else if(N == preorder){ cout << "preorder : "; preOrder(root); } else if(N == postorder){ cout << "postorder : "; postOrder(root); } cout << '\n'; } private: void insertNode(T value, Node<T> *&currentNode){ if(currentNode == nullptr) currentNode = new Node<T>(value); else{ if(value <= currentNode->data) insertNode(value,currentNode->left); else insertNode(value, currentNode->right); } } bool searchNode(T value,Node<T> *current){ if(current->data == value) return 1; if(value < current->data) searchNode(value, current->left); else searchNode(value,current->right); return 0; } void getleftMost(Node<T> *&current){ Node<T> *ptr = current->left, *prev = current; while(ptr->right != nullptr){ prev = ptr; ptr = ptr->right; } prev->right = nullptr; current->data = ptr->data; delete ptr; } void removeNode(T value, Node<T> *&current){ if(current != nullptr){ if(value < current->data) removeNode(value,current->left); else if(value > current->data) removeNode(value,current->right); else if (value == current->data){ if(current->left == nullptr){ Node<T> *ptr = current; current = current->right; delete ptr; } else if(current->right == nullptr){ Node<T> *ptr = current; current = current->left; delete ptr; } else{ getleftMost(current); } } } } void inOrder(Node<T>* current){ if(current != nullptr){ inOrder(current->left); cout << "[ " << current->data << " ] "; inOrder(current->right); } } void preOrder(Node<T>* current){ if(current != nullptr){ cout << "[ " << current->data << " ] "; preOrder(current->left); preOrder(current->right); } } void postOrder(Node<T>* current){ if(current != nullptr){ postOrder(current->left); postOrder(current->right); cout << "[ " << current->data << " ] "; } } }; int main(){ BinaryTree<int> test; int k[] = {3, 9, 4, 1, 10, 5, 9, 10, 7, 2}; for(int i = 0; i < 10; i++) test.insert(k[i]); test.print(inorder); test.print(preorder); test.print(postorder); test.remove(3); test.print(inorder); test.print(preorder); test.print(postorder); return 0; } 코드 내에서는 빈 트리에 3, 9, 4, 1, 10, 5, 9, 10, 7, 2를 순서대로 삽입을 진행합니다. 그 과정은 다음과 같습니다. 여기서 inorder, preorder, postorder가 있는데, 이는 이진 트리 순회 방법입니다. 특정한 순서로 각 노드를 방문하여 최종적으로 트리의 모든 노드를 방문하는 방법을 말합니다. inorder traversal : 왼쪽 자식 노드, 자신, 오른쪽 자식 노드의 순서로 순회하는 방법입니다. preorder traversal : 자신, 왼쪽 자식 노드, 오른쪽 자식 노드의 순서로 순회하는 방법입니다. postorder traversal : 왼쪽 자식 노드, 오른쪽 자식 노드, 자신의 순서로 순회하는 방법입니다. result inorder : [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 7 ] [ 9 ] [ 9 ] [ 10 ] [ 10 ] preorder : [ 3 ] [ 1 ] [ 2 ] [ 9 ] [ 4 ] [ 5 ] [ 9 ] [ 7 ] [ 10 ] [ 10 ] postorder : [ 2 ] [ 1 ] [ 7 ] [ 9 ] [ 5 ] [ 4 ] [ 10 ] [ 10 ] [ 9 ] [ 3 ] removed 3 inorder : [ 1 ] [ 2 ] [ 4 ] [ 5 ] [ 7 ] [ 9 ] [ 9 ] [ 10 ] [ 10 ] preorder : [ 2 ] [ 1 ] [ 9 ] [ 4 ] [ 5 ] [ 9 ] [ 7 ] [ 10 ] [ 10 ] postorder : [ 1 ] [ 7 ] [ 9 ] [ 5 ] [ 4 ] [ 10 ] [ 10 ] [ 9 ] [ 2 ] 예시로 보여드린 트리의 구조가 매우 비효율적입니다. 이러한 구조의 트리의 경우, 삽입, 삭제, 탐색 연산의 시간 복잡도가 증가하게 됩니다. 이러한 문제에 대한 해결 방안으로 Height Balanced Tree 중에서, AVL Tree와 Red-Black Tree에 대해서 알아보도록 하겠습니다. 물론 내일..

Data Structure · 2024-07-05

스택, 큐

Stack Stack은 FILO(First In Last Out) 형식의, 가장 먼저 추가된 데이터가 가장 나중에 삭제되는 자료구조입니다. 헬스를 하면서 바벨에 원판 끼우고 뺄 때, 가장 나중에 넣은 원판을 가장 먼저 빼는 것, 이것이 스택 자료구조라고 보면 됩니다. 스택은 프로세스 메모리 상에서 임시 로컬 데이터를 저장하는데 쓰이기도 합니다. 예를 들어 C++ 프로그램을 실행하면 코드 내 함수 파라미터, 지역 변수, 리턴 값 등이 이 스택 자료구조에 저장됩니다. 스택에는 push 연산과 pop 연산이 있는데, push 연산은 마지막에 노드를 추가하는 연산이고, pop은 가장 마지막 노드를 제거하는 연산입니다. 스택은 보통 배열 또는 연결리스트를 통해서 구현을 합니다. by Linked List code #include<iostream> #include<ostream> #define MAX 10 class Underflow {}; using namespace std; template <typename T> class Node { public: T data; Node<T> *next; Node<T>() : next(nullptr) {} Node<T>(T value, Node<T>* next1) : data(value), next(next1) {} }; template <typename T> class Stack { public: int length; Node<T> *top; Stack<T>() : length(0), top(nullptr) {} bool empty(){ return (length ? false : true); } void push(T value){ top = new Node<T>(value, top); length++; } T pop(){ try{ if(length == 0) throw Underflow(); T returnValue = top->data; Node<T> *ptr = top; top = top->next; delete ptr; length--; return returnValue; } catch(Underflow e){ cout << "Underflow occurs" << '\n'; exit(0); } } ~Stack<T>(){ Node<T> *ptr = top, *prev; while(ptr != nullptr){ prev = ptr; ptr = ptr->next; delete prev; } } }; template <typename T> ostream& operator<< (ostream& scan, Stack<T> &inputArr){ Node<T> *ptr = inputArr.top; while(ptr != nullptr){ scan << "[ " << ptr->data << " ]-"; ptr = ptr->next; } scan << "[ NULL ]" << '\n'; } int main(){ Stack<int> test; int k = 4; for(int i = 0; i < MAX; i++) test.push(k++); cout << test; test.pop(); cout << test; return 0; } result [ 13 ]-[ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ] [ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ] by Array code #include<iostream> #include<ostream> #define MAX 10 class Underflow {}; using namespace std; template <typename T> class Stack { public: int length; int top; T* arr; Stack<T>() : length(0), top(-1) {} Stack<T>(int size) : length(size), top(-1) { arr = new T(size); } ~Stack<T>(){ delete[] arr; } bool empty(){ return (length ? false : true); } bool full(){ return (top == length - 1 ? true : false); } void push(T value){ if(full()){ T* newArr = new T[length + MAX]; for(int i = 0; i < length; i++) newArr[i] = arr[i]; delete[] arr; arr = newArr; } arr[++top] = value; } T pop(){ try{ if(top < 0) throw Underflow(); return arr[top--]; } catch(Underflow e){ cout << "underflow occurs" << '\n'; exit(0); } } }; template <typename T> ostream& operator<< (ostream& scan, Stack<T> &inputArr){ for(int i = inputArr.top; i >= 0; i--) scan << "[ " << inputArr.arr[i] << " ]-"; scan << "[ NULL ]" << '\n'; } int main(){ Stack<int> test; int k = 4; for(int i = 0; i < MAX; i++) test.push(k++); cout << test; test.pop(); cout << test; return 0; } result [ 13 ]-[ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ] [ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ] Queue Queue는 FIFO (First In First Out) 의 형태로, 가장 먼저 추가된 노드가 가장 먼저 삭제되는 자료구조이다. 도로 신호등에 걸린 차량들을 생각해보았을 때, 신호등이 초록불이 되면 먼저 도착해 정지했던 차량이 먼저 출발하는데, 큐가 이러한 구조로 되어있다. 큐는 enqueue와 dequeue 연산이 있는데, enqueue는 가장 마지막에 새로운 노드를 추가하는 연산이고, dequeue는 가장 앞에 있는 (가장 먼저 추가됐었던) 노드를 삭제하는 연산이다. 이러한 큐 자료구조는 한 예로 실행가능한 상태의 프로세스들이 CPU 자원을 할당받고자 대기 중일 때, 이러한 큐 자료구조 형태로 저장된다. By Linked List code #include<iostream> #include<ostream> #define MAX 10 class Underflow {}; using namespace std; template <typename T> class Node { public: T data; Node<T> *next; Node<T>() : next(nullptr) {} Node<T>(T value, Node<T> *next1) : data(value), next(next1) {} }; template <typename T> class Queue { public: int length; Node<T> *front, *rear; Queue<T>() : length(0), front(nullptr), rear(nullptr) {} ~Queue<T>(){ Node<T> *ptr = front,*prev; while(ptr != nullptr){ prev = ptr; ptr = ptr->next; delete prev; } } bool empty() {return (length? false : true);} void enqueue(T value){ if(length == 0) front = rear = new Node<T>(value, nullptr); else{ rear->next = new Node<T>(value, nullptr); rear = rear->next; } length++; } T dequeue(){ try{ if(empty()) throw Underflow(); Node<T> *ptr = front; T returnValue = ptr->data; front = front->next; delete ptr; length--; return returnValue; } catch(Underflow e){ cout << "underflow occurs" << '\n'; exit(0); } } }; template <typename T> ostream& operator<< (ostream& scan, Queue<T>& inputQueue){ Node<T> *ptr = inputQueue.front; scan << "front-"; while(ptr !=nullptr){ scan << "[ " << ptr->data << " ]-"; ptr = ptr->next; } scan << "rear" << '\n'; } int main(){ Queue<int> test; int k = 3; for(int i = 0; i < MAX; i++) test.enqueue(k++); cout << test; test.dequeue(); cout << test; return 0; } result front-[ 3 ]-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear By Array 큐의 한 형태로 원형 큐 (Circular Queue)가 있는데, 이는 배열을 통해 큐를 구현하였을 때, 배열의 크기는 고정된다는 특징으로 저장 공간이 부족하다는 단점을 해결한 형태의 큐입니다. enqueue rear 인덱스 값에 1을 더해 업데이트하고, rear 인덱스 값에 데이터를 삽입합니다. 만약 rear의 인덱스 값이 배열의 크기 이상이 되면 rear 값을 0으로 초기화합니다. dequeue 배열의 front 인덱스에 해당하는 데이터을 리턴하고, front 인덱스 값에 1을 더해 업데이트 합니다. enqueue의 rear와 마찬가지로 front 값이 배열의 크기 이상이 되면 rear 값을 0으로 초기화합니다. code #include<iostream> #include<ostream> #define MAX 10 using namespace std; class Underflow {}; class Overflow {}; template <typename T> class Queue { public: int length; int front,rear; T *arr; Queue<T>() : length(0), front(-1), rear(-1) { arr = new T[MAX]; } ~Queue<T>(){ delete[] arr; } bool full(){ return (length == MAX ? 1 : 0); } bool empty(){ return (length? 0 : 1); } void enqueue(T value){ try{ if(full()) throw Overflow(); rear++; if(rear >= MAX) rear %= MAX; if(length == 0) front = rear; arr[rear] = value; length++; } catch(Overflow e){ cout << "overflow occurs" << '\n'; exit(0); } } T dequeue(){ try{ if(empty()) throw Underflow(); T returnValue = arr[front]; if(front == rear) front = rear = -1; else front++; if(front >= MAX) front %= MAX; length--; return returnValue; } catch(Underflow e){ cout << "underflow occurs" << '\n'; exit(0); } } }; template <typename T> ostream& operator<<(ostream& scan, Queue<T>& inputQueue){ scan << "front-"; int idx = inputQueue.front; while(1){ scan << "[ " << inputQueue.arr[idx] << " ]-"; if(idx == inputQueue.rear) break; idx++; if(idx >= MAX) idx %= MAX; } scan << "rear" << '\n'; } int main(){ Queue<int> test; int k = 3; for(int i = 0; i < MAX; i++) test.enqueue(k++); cout << test; test.dequeue(); cout << test; test.enqueue(k); cout << test; return 0; } result front-[ 3 ]-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-[ 13 ]-rear Queue By Two Stack 두개의 스택을 통해서 큐를 구현할 수 있습니다. 기본적으로 데이터가 저장되는 스택1과 dequeue 작업을 위해 데이터를 임시적으로 저장할 스택2가 필요한데, enqueue연산의 경우 스택1에 push 연산을 통해 스택의 경우와 똑같이 저장합니다. dequeue연산을 위해서는 가장 밑에 있는 데이터를 추출해야 하는데, 스택의 경우, FILO 구조로 가장 위의 있는 데이터가 먼저 추출될 수 밖에 없다. 여기서 임시 저장소 스택2가 사용되는데, 먼저 스택1에 저장된 데이터들을 가장 밑에 있는 데이터가 나올 때까지 pop 연산을 진행합니다. 그리고 각 연산마다 추출되는 데이터를 스택2에 그대로 push 연산을 진행합니다. 그러면 마지막엔 스택2에는 가장 밑에 있던 데이터를 제외한 나머지 노드들이 삽입된 순서의 반대로 저장되어있을텐데, 밑에 있던 데이터를 추출한 후, 스택2 안에 데이터가 모두 사라질 때까지 pop연산을 진행하고, 연산을 통해 추출된 데이터들을 다시 스택1에 push 연산을 진행합니다. 스택1에서 pop 연산 진행 추출된 데이터를 스택2에 push 연산 진행 1,2 단계를 스택1의 가장 밑에 있는 데이터가 추출될 때까지 진행 목표 데이터 추출 스택2에서 pop연산 진행 추출된 데이터를 스택1에 push연산 진행 5,6 단계를 스택2에 아무 데이터도 남지 않을 때까지 진행 마찬가지로 스택 또한 두개의 큐를 통해서 구현할 수 있습니다.

Data Structure · 2024-07-04

연결 리스트

블렌더 모델링 너무 힘들어서 머리 좀 식히고자 복습할 겸 작성합니다.. Linked List 연결리스트는 각 노드가 연속되어 저장되는 배열과 달리, 각 노드들의 위치가 연속되지 않지만, 각자 다음 노드의 위치 정보를 함께 저장하여 연결되는 자료구조입니다. 각 노드는 데이터와 다른 노드에 대한 포인터가 저장된다. 연결리스트는 노드의 추가, 삭제에 있어서 특정 노드들의 연결만 업데이트하면 되므로 배열보다 월등히 빠르다. 그러나 특정 노드에 접근하기 위해서는 첫 노드로부터 순차적으로 접근해야하기 때문에 리스트의 노드 수에 따라서 선형적이며, 특정 노드와의 연결이 끊어지게 되는 경우, 끊어진 노드와 연결된 다른 노드들의 정보도 잃어버린다는 단점이 있다. Singly Linked List Singly Linked List는 단순히 각 노드가 다음 노드의 포인터만을 가지고 있는 연결 리스트이다. 이는 운영체제의 파일 시스템에서 연속 할당 (Contiguous Allocation) 방식에서 사용되기도 한다. code #include<iostream> #include<ostream> #define MAX 10 using namespace std; class InvalidIndex {}; class Underflow {}; template <typename T> class Node{ public: T data; Node<T> *nextNode; Node<T>() : nextNode(nullptr) {} Node<T>(T value, Node<T> *next1) : data(value), nextNode(next1) {}; ~Node<T>(){ nextNode = nullptr; } }; template <typename T> class LinkedList{ public: int length; Node<T> *head; LinkedList() : length(0), head(nullptr) {} ~LinkedList(){ Node<T> *ptr1 = head, *ptr2; while(ptr1 != nullptr){ ptr2 = ptr1; ptr1 = ptr1->nextNode; delete ptr2; } } int size(){ return length; } void insert(int idx, T value){ try { if(idx < 0 || idx > length) throw InvalidIndex(); if(idx == 0) head = new Node<T>(value, head); else{ Node<T> *ptr = head; for(int i = 0; i < idx - 1; i++) ptr = ptr->nextNode; ptr->nextNode = new Node<T>(value,ptr->nextNode); } length++; } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } } void erase(int idx){ try{ if(length <= 0) throw Underflow(); if(idx < 0 || idx >= length) throw InvalidIndex(); Node<T> *ptr = head; if(idx == 0){ head = head->nextNode; delete ptr; } else{ for(int i=0; i < idx - 1;i++) ptr = ptr->nextNode; Node<T> *deletedNode = ptr->nextNode; ptr->nextNode = deletedNode->nextNode; delete deletedNode; } length--; } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } catch(Underflow e){ cout << "underflow" << '\n'; } } bool serach(T value){ Node<T> *ptr = head; while(ptr != nullptr){ if(ptr->data == value) return 1; ptr = ptr->nextNode; } return 0; } T& operator[] (int idx){ Node<T> *ptr = head; for(int i=0 ; i < idx; i++) ptr = ptr->nextNode; return ptr->data; } }; template <typename T> ostream& operator <<(ostream &scan, LinkedList<T> &inputArr){ Node<T> *ptr = inputArr.head; while(ptr != nullptr){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->nextNode; } scan << "[ NULL ]" << '\n'; } int main(){ LinkedList<int> test; int k = 4; for(int i = 0; i < MAX; i ++) test.insert(i,k); cout << test; return 0; } result [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ NULL ] Doubly Linked List Doubly Linked List는 각 노드가 다음 노드의 포인터와 이전 노드의 포인터를 저장하여, 이중으로 연결된 연결리스트를 말한다. 각 노드가 이중으로 연결되었기 때문에, 혹여나 특정 노드가 다음 노드와의 연결이 끊어지더라도, 끊어진 다음 노드에 저장된 이전 노드 포인터를 이용하여 복원할 수 있다는 장점이 있다. code #include<iostream> #include<ostream> #define MAX 10 using namespace std; class InvalidIndex {}; class Underflow {}; template <typename T> class Node { public: T data; Node<T> *prev, *next; Node<T>() : prev(nullptr), next(nullptr) {} Node<T>(T value, Node<T> *prev1, Node<T> *next1) : data(value), prev(prev1), next(next1) {} }; template <typename T> class DoublyLinkedList { public: int length; Node<T> *head, *tail; DoublyLinkedList<T>() : length(0), head(nullptr), tail(nullptr) {} int size() { return length; } void insert(int idx, T value){ try { if(idx < 0 || idx > length) throw InvalidIndex(); if(idx == 0) { head = new Node<T>(value, nullptr, head); if(length == 0) tail = head; else head->next->prev = head; } else{ tail = new Node<T>(value,tail,nullptr); tail->prev->next = tail; } length++; } catch(InvalidIndex e) { cerr << "invalid index" << '\n'; exit(0); } } void erase(int idx){ try{ if(!length) throw Underflow(); if(idx < 0 || idx >= length) throw InvalidIndex(); if(idx == 0){ Node<T> *ptr = head; head = head->next; head->prev = nullptr; delete ptr; } else if(idx == length - 1){ Node<T> *ptr = tail; tail = tail->prev; tail->next = nullptr; delete ptr; } else{ if(idx >= (length - 1) / 2.0){ Node<T> *ptr = tail; for(int i = length - 1; i > idx + 1; i--) ptr = ptr->prev; Node<T> *erasedNode = ptr->prev; ptr->prev = erasedNode->prev; ptr->prev->next = ptr; delete erasedNode; } else{ Node<T> *ptr = head; for(int i = 0; i < idx - 1; i++) ptr = ptr->next; Node<T> *eraseNode = ptr->next; ptr->next = eraseNode->next; ptr->next->prev = ptr; delete eraseNode; } } length--; } catch(Underflow e){ cout << "underflow occur" << '\n'; exit(0); } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } } }; template <typename T> ostream& operator <<(ostream &scan, DoublyLinkedList<T> &inputArr){ Node<T> *ptr = inputArr.head; scan << "[ NULL ] - "; while(ptr != nullptr){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->next; } scan << "[ NULL ]" << '\n'; } template <typename T> ostream& operator >>(ostream &scan, DoublyLinkedList<T> &inputArr){ Node<T> *ptr = inputArr.tail; scan << "[ NULL ] - "; while(ptr != nullptr){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->prev; } scan << "[ NULL ]" << '\n'; } int main(){ DoublyLinkedList<int> test; int k = 4; for(int i = 0; i < MAX; i ++) test.insert(i,k++); cout << test << '\n'; cout >> test << '\n'; test.erase(7); cout << "delete indxe.7\n" << test << '\n'; test.erase(2); cout << "delete index.2\n" << test << '\n'; return 0; } result [ NULL ] - [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ NULL ] [ NULL ] - [ 13 ] - [ 12 ] - [ 11 ] - [ 10 ] - [ 9 ] - [ 8 ] - [ 7 ] - [ 6 ] - [ 5 ] - [ 4 ] - [ NULL ] delete indxe.7 [ NULL ] - [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ NULL ] delete index.2 [ NULL ] - [ 4 ] - [ 5 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ NULL ] Circular Linked List Circular Linked List는 tail, 마지막 노드가 head, 처음 노드와 연결된 구조를 말한다. 순차적으로 재생되는 음악 재생목록이라고 보면 된다. code ##include<iostream> ##include<ostream> ##define MAX 10 using namespace std; class InvalidIndex {}; class Underflow {}; template <typename T> class Node { public: T data; Node<T> *prev, *next; Node<T>() : prev(nullptr), next(nullptr) {} Node<T>(T value, Node<T> *prev1, Node<T> *next1) : data(value), prev(prev1), next(next1) {} }; template <typename T> class CircularLinkedList { public: int length; Node<T> *head, *tail; CircularLinkedList<T>() : length(0), head(nullptr), tail(nullptr) {} int size(){ return length; } void insert(int idx, T value){ try{ if(idx < 0 || idx > length) throw InvalidIndex(); if(idx == 0){ head = new Node<T>(value, tail, head); if(length == 0) tail = head; else head->next->prev = head; } else{ tail = new Node<T>(value,tail,head); tail->prev->next = tail; tail->next->prev = tail; } length++; } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } } void erase(int idx){ try{ if(!length) throw Underflow(); if(idx < 0 || idx >= length) throw InvalidIndex(); if(idx == 0){ Node<T> *ptr = head; head = head->next; head->prev = tail; tail->next = head; delete ptr; } else if(idx == length - 1){ Node<T> *ptr = tail; tail = tail->prev; tail->next = head; head->prev = tail; delete ptr; } else{ if(idx >= (length - 1) / 2.0){ Node<T> *ptr = tail; for(int i = length - 1; i > idx + 1; i--) ptr = ptr->prev; Node<T> *erasedNode = ptr->prev; ptr->prev = erasedNode->prev; ptr->prev->next = ptr; delete erasedNode; } else{ Node<T> *ptr = head; for(int i = 0; i < idx - 1; i++) ptr = ptr->next; Node<T> *erasedNode = ptr->next; ptr->next = erasedNode->next; ptr->next->prev = ptr; delete erasedNode; } } length--; } catch(Underflow e){ cout << "underflow occur" << '\n'; exit(0); } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } } }; template <typename T> ostream& operator <<(ostream &scan, CircularLinkedList<T> &inputArr){ Node<T> *ptr = inputArr.head; for(int i = 0; i < inputArr.size(); i++){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->next; } scan << "[ " << ptr->data << " ]" << '\n'; } template <typename T> ostream& operator >>(ostream &scan, CircularLinkedList<T> &inputArr){ Node<T> *ptr = inputArr.tail; for(int i = inputArr.size() - 1; i >= 0; i--){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->prev; } scan << "[ " << ptr->data << " ]" << '\n'; } int main(){ CircularLinkedList<int> test; int k = 4; for(int i = 0; i < MAX; i ++) test.insert(i,k++); cout << test << '\n'; cout >> test << '\n'; test.erase(7); cout << "delete indxe.7\n" << test << '\n'; test.erase(2); cout << "delete index.2\n" << test << '\n'; return 0; } result [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ 4 ] [ 13 ] - [ 12 ] - [ 11 ] - [ 10 ] - [ 9 ] - [ 8 ] - [ 7 ] - [ 6 ] - [ 5 ] - [ 4 ] - [ 13 ] delete indxe.7 [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ 4 ] delete index.2 [ 4 ] - [ 5 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ 4 ]

Data Structure · 2024-07-03

이승준

Contact

학교 공부